home *** CD-ROM | disk | FTP | other *** search
/ Languguage OS 2 / Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO / gnu / libg_261.zip / libg_261 / libg++ / etc / trie-gen / trie.cc < prev    next >
C/C++ Source or Header  |  1994-05-13  |  7KB  |  199 lines
  1. /* Generates a minimal-prefix trie for a user-specified set of keywords.
  2.  
  3.    Copyright (C) 1989, 1993 Free Software Foundation, Inc.
  4.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  5.    
  6.    This file is part of GNU TRIE-GEN.
  7.    
  8.    GNU TRIE-GEN is free software; you can redistribute it and/or modify
  9.    it under the terms of the GNU General Public License as published by
  10.    the Free Software Foundation; either version 1, or (at your option)
  11.    any later version.
  12.    
  13.    GNU TRIE-GEN is distributed in the hope that it will be useful,
  14.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.    GNU General Public License for more details.
  17.    
  18.    You should have received a copy of the GNU General Public License
  19.    along with GNU trie-gen; see the file COPYING.  If not, write to
  20.    the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  21.  
  22. #include <stdio.h>
  23. #include <std.h>
  24. #include <limits.h>
  25. #include <new.h>
  26. #include "renew.h"
  27. #include "options.h"
  28. #include "trie.h"
  29.  
  30. const int      MAX_ASCII        = 128;
  31.  
  32. /* Insert a new keyword into the data structure, possibly growing the
  33.    keyword table to accomodate the new entry.  Space for STR has already
  34.    been allocated in the caller.  In addition, the MAX_KEY_LEN is updated
  35.    if the current LEN is larger than the previous max.  This information
  36.    is needed later on when dynamically allocating the TRIE table. */
  37.    
  38. void 
  39. Trie::insert (char *str, int len)
  40. {
  41.   if (current_size >= total_size)
  42.     resize (total_size * 2);
  43.   keys[current_size++] = str;
  44.   if (max_key_len < len)
  45.     max_key_len = len;
  46. }
  47.  
  48. /* Grow the KEYS table to allow a maximum of NEW_SIZE entries. 
  49.    Old keys are copied into the new buffer. */
  50.  
  51. void 
  52. Trie::resize (int new_size)
  53. {
  54.   keys = new (keys, total_size = new_size) char *;
  55. }
  56.  
  57. /* Write the generated TRIE out as a static table.  Compaction is
  58.    performed if the user requests it, otherwise the table is 
  59.    not compacted at all! (this leads to ridiculously large tables; perhaps
  60.    compaction should be the default?) */
  61.  
  62. void 
  63. Trie::output (void)
  64. {
  65.   if (current_size <= 0)
  66.     return;
  67.   else
  68.     {
  69.       sort ();
  70.  
  71.       fputs ("#include <string.h>\n#define MAX_ASCII 128\n\nstatic", stdout);
  72.       if (option[CONST])
  73.         fputs (" const", stdout);
  74.       fputs (" char *const word_list[] = \n{\n  \"\",\n", stdout);
  75.  
  76.       for (int i = 0; i < current_size; i++) 
  77.         printf ("  \"%s\",\n", keys[i]);
  78.  
  79.       fflush (stdout);
  80.       fputs ("};\n\n", stdout);
  81.       build (current_size);
  82.  
  83.       if (option[COMPACT])
  84.         matrix.output ();
  85.       else
  86.         {
  87.           const int MAX_NUMBER
  88.         = (current_size > max_row) ? current_size : max_row;
  89.           int   field_width;
  90.           int   count = MAX_NUMBER;
  91.  
  92.           for (field_width = 2; (count /= 10) > 0; field_width++)
  93.             ;
  94.  
  95.           printf ("static const %s trie_array[][MAX_ASCII] = \n{", 
  96.                   MAX_NUMBER < SCHAR_MAX ?
  97.             (CHAR_MIN == 0 ? "signed char" : "char") :
  98.                   MAX_NUMBER < SHRT_MAX ? "short" : "int");
  99.  
  100.           for (i = 0; i < max_row; i++)
  101.             {
  102.               fputs ("\n  ", stdout);
  103.  
  104.               for (int j = 0; j < MAX_ASCII; j++)
  105.                 printf ("%*d,", field_width, matrix (i, j));
  106.             }
  107.           fputs ("\n};\n", stdout);
  108.         }
  109.  
  110.       printf ("\n%schar *\nin_word_set (const char *str, int len)\n{\n"
  111.               "  %schar *s = %sstr;\n  int i = 0;\n\n"
  112.               "  while ((i = %s) > 0)\n    ;\n\n"
  113.               "  return i == 0 || strncmp (s = word_list[-i], str, len)"
  114.               " ? 0 : s;\n}\n",
  115.               option[CONST] ? "const " : "",
  116.               option[CONST] ? "const " : "",
  117.               option[CONST] ? "" : "(char*)",
  118.               option[COMPACT] ? "next_state(i, *s++)" : "trie_array[i][*s++]");
  119.     }
  120. }
  121.  
  122. /* Comparison routine called by qsort. */
  123. int 
  124. Trie::cmp (char **s1, char **s2)
  125. {
  126.   return strcmp (*s1, *s2);
  127. }
  128.  
  129. /* Sort the keys by lexicographical order. */
  130.  
  131. void 
  132. Trie::sort (void)
  133. {
  134.   typedef int (*PTF)(const void *, const void *);
  135.   qsort ((void *) keys, current_size, sizeof *keys, PTF (cmp));
  136. }
  137.  
  138. /* Generate the trie, using recursive calls if necessary to handle 
  139.    duplicate keyword index positions. */
  140.  
  141. void 
  142. Trie::build (int hi, int lo, int col)
  143. {
  144.   if (option[FULL])
  145.     {
  146.       int row = max_row - 1;
  147.  
  148.       /* Process each key in the range lo..hi, possibly calling the function
  149.          recursively when duplicate consecutive characters are found (that's
  150.          why it is important to sort the keywords first!).  Note that calls
  151.          to member function MATRIX build the internal form used to generate 
  152.          the compacted sparse array.  Positive values indicate the next row
  153.          (which really encodes DFA states) to consider; negative values
  154.          are flags that provide (when negated) the correct offset into a generated 
  155.          array of strings. */
  156.       
  157.       for (int i = lo; i < hi; i++)
  158.         if (keys[i][col] == '\0')
  159.           matrix (row, keys[i][col], -i - 1);
  160.         else
  161.           {
  162.             /* Location the end of the duplicate characters in the current column. */
  163.             
  164.             for (lo = i; i < hi - 1 && keys[i][col] == keys[i + 1][col]; i++)
  165.               ;
  166.             
  167.             matrix (row, keys[lo][col], max_row++);
  168.             build (i + 1, lo, col + 1);
  169.           }
  170.     } 
  171.   else
  172.     {
  173.       int row = max_row - 1;
  174.  
  175.       /* Process each key in the range lo..hi, possibly calling the function
  176.          recursively when duplicate consecutive characters are found (that's
  177.          why it is important to sort the keywords first!).  Note that calls
  178.          to member function MATRIX build the internal form used to generate 
  179.          the compacted sparse array.  Positive values indicate the next row
  180.          (which really encodes DFA states) to consider; negative values
  181.          are flags that provide (when negated) the correct offset into a generated 
  182.          array of strings. */
  183.       
  184.       for (int i = lo; i < hi; i++)
  185.         if (keys[i][col] == '\0' || i == hi - 1 || keys[i][col] != keys[i + 1][col])
  186.           matrix (row, keys[i][col], -i - 1);
  187.         else
  188.           {
  189.             /* Location the end of the duplicate characters in the current column. */
  190.             
  191.             for (lo = i; i < hi - 1 && keys[i][col] == keys[i + 1][col]; i++)
  192.               ;
  193.             
  194.             matrix (row, keys[lo][col], max_row++);
  195.             build (i + 1, lo, col + 1);
  196.           }
  197.     } 
  198. }  
  199.